package com.lht.arithmetic.skipList;

import java.util.HashMap;
import java.util.Map;

/**
 * 自己设计跳跃表
 * 自己定义跳跃表规范:
 * 1. 最底层所以，至少4个 （考虑做成参数， 可配置）
 * 2. 每8个元素，生成一个索引  一头 一尾 (考虑做成参数，可配置)
 *
 * @author Eric
 * @version 1.0
 * @date 2019-10-07
 */
public class SkipList<T extends Comparable<T>> {

    /**
     * 链表长度
     */
    private int capacity = 0;

    /**
     * 跳跃表 索引高度 默认是 1 是没高度，直接走链表
     */
    private int height = 1;

    /**
     * 顶层索引 元素个数
     */
    private int topNumber = 4;

    /**
     * 链表长度 大于这个值分裂   groupNumber*topNumber 如果当前层大于 roupNumber*topNumber个元素 则索引向上升级
     */
    private int groupNumber = 8;

    /**
     * 链表头
     */
    private SkipNode<T> header;

    /**
     * 链表尾
     */
    private SkipNode<T> tail;


    public SkipNode<T> search(T data, SkipNode<T> search, int height) {
        if (data == null) {
            return null;
        }
        if (data.compareTo(this.header.getVal()) < 0) {
            return null;
        }
        if (data.compareTo(this.tail.getVal()) > 0) {
            return null;
        }
        return baseSearch(data, this.header, this.height);
    }

    /**
     * 查询方法 ,相当于 根据实例，查询出下标，但是链表没下标，返回链表实例包装类
     *
     * @param data 1
     * @return com.lht.arithmetic.skipList.MySkipList
     * @throws
     * @author Eric
     * @date 2019/10/7
     **/
    private SkipNode<T> baseSearch(T data, SkipNode<T> search, int height) {
        SkipNode node = null;
        if (height == 0) {
            //直接查询链表
            int num = groupNumber;
            SkipNode begin = search;
            while (begin != null && num > 0) {
                if (data.equals(begin.getVal())) {
                    node = begin;
                }
                begin = begin.getNext();
                num--;
            }
        } else {
            int curHeight = height;
            //在这个层次找 ，这样可以获取元素的下个元素
            SkipNode<T> one = search;
            SkipNode<T> two = one.getIndexes().get(curHeight);
            while (one != null) {
                if (data.compareTo(one.getVal()) > 0 && data.compareTo(two.getVal()) < 0) {
                    search(data, one, --curHeight);
                }
                one = two;
                two = one.getIndexes().get(curHeight);
            }
        }
        return node;
    }


    public boolean add(T data) {
        if (data == null) {
            return false;
        }
        boolean add = baseAdd(data, this.header, this.height);
        if (add) {
            this.capacity++;
        }
        //扩充索引
        updateIndxe();

        return add;
    }

    private boolean baseAdd(T data, SkipNode<T> search, int height) {
        if (this.header == null) {
            this.header = new SkipNode<T>(data, null, this.tail);
            return true;
        }
        if (data.compareTo(this.header.getVal()) < 0) {
            SkipNode<T> cur = new SkipNode<>(data, null, this.header);
            this.header.setPrefix(cur);
            header = cur;
            return true;
        }
        if (this.tail == null) {
            this.tail = new SkipNode<T>(data, this.header, null);
            this.header.setNext(this.tail);
            return true;
        }
        if (data.compareTo(this.tail.getVal()) >= 0) {
            SkipNode<T> cur = new SkipNode<>(data, this.tail, null);
            this.tail.setNext(cur);
            tail = cur;
            return true;
        }
        if (height == 1) {
            //直接查询链表
            SkipNode<T> tmp = search;
            while (tmp != null) {
                //如果已经是链表末尾
                if (data.compareTo(tmp.getVal()) >= 0) {
                    if(data.compareTo(tmp.getNext().getVal()) < 0) {
                        SkipNode<T> cur = new SkipNode<>(data, tmp, tmp.next);
                        tmp.setNext(cur);
                        tmp.getNext().setPrefix(cur);
                        return true;
                    }else {
                        if (tmp.next == null) {
                            System.out.println("错误：" + data);
                        }
                    }
                }
                tmp = tmp.getNext();
            }
        } else {
            int curHeight = height;
            //在这个层次找 ，这样可以获取元素的下个元素
            SkipNode<T> one = search;
            SkipNode<T> two = one.getIndexes().get(curHeight);
            while (one != null && two != null) {
                if (data.compareTo(one.getVal()) > 0 && data.compareTo(two.getVal()) < 0) {
                    search(data, one, --curHeight);
                }
                one = two;
                two = one.getIndexes().get(curHeight);
            }
        }
        return false;
    }

    private void updateIndxe() {
        //变更跳跃表索引
        int curIndex = 1;
        int totalNumber = this.capacity;
        while (totalNumber >= this.topNumber * this.groupNumber) {
            //需要统计 第一层索引元素数据量
            int curIndexNumber = 0;
            if (curIndex == 1) {
                // 第一层 ,链表填装
                SkipNode<T> node = this.header;
                SkipNode<T> tmp = this.header;
                int i = 1;
                while (tmp != null) {
                    if (i % this.groupNumber == 0) {
                        node.getIndexes().put(curIndex, tmp);
                        node = tmp;
                        curIndexNumber++;
                    }
                    i++;
                    tmp = tmp.getNext();
                }
            } else {
                // 上层，遍历下层填装
                SkipNode<T> node = this.header;
                SkipNode<T> tmp = this.header;
                int i = 1;
                while (tmp != null) {
                    if (i % this.groupNumber == 0) {
                        node.getIndexes().put(curIndex, tmp);
                        node = tmp;
                        curIndexNumber++;
                    }
                    i++;
                    tmp = tmp.getIndexes().get(curIndex - 1);
                }
            }
            totalNumber = curIndexNumber;
            if (totalNumber >= this.topNumber * this.groupNumber) {
              curIndex++;
            }
        }
        this.height = curIndex;
    }

    public boolean remove(T data) {
        if (data == null) {
            return false;
        }
        if (data.compareTo(this.header.getVal()) < 0) {
            return false;
        }
        if (data.compareTo(this.tail.getVal()) > 0) {
            return false;
        }
        boolean success = baseRemove(data, this.header, this.height);
        if (success) {
            this.capacity--;
        }
        return success;
    }

    /**
     * 遍历 输出方法用来测试
     *
     * @return void
     * @throws
     * @author Eric
     * @date 2019/10/7
     **/
    public void list() {
        int num = 0;
        SkipNode<T> tmp = this.header;
        System.out.print("[");
        while (tmp != null) {
            System.out.print(tmp.getVal() + ",");
            tmp = tmp.next;
            num++;
        }
        System.out.println("]");
        System.out.println("元素总数： " + num);
    }

    /**
     * 遍历输出 索引
     *
     * @return void
     * @throws
     * @author Eric
     * @date 2019/10/7
     **/
    public void indexList() {
        int curH = this.height;
        while (curH > 0) {
            SkipNode<T> tmp = this.header;
            System.out.print("[");
            while (tmp != null) {
                System.out.print(tmp.getVal() + ",");
                tmp = tmp.getIndexes().get(curH);
            }
            System.out.println("]");
            curH--;
        }
    }

    private boolean baseRemove(T data, SkipNode<T> search, int height) {
        boolean success = false;
        if (height == 0) {
            //直接查询链表
            int num = groupNumber;
            SkipNode<T> begin = search;
            while (begin != null && num > 0) {
                if (data.equals(begin.getVal())) {
                    begin.getPrefix().setNext(begin.getNext());
                    success = true;
                    break;
                }
                begin = begin.getNext();
                num--;
            }
        } else {
            int curHeight = height;
            //在这个层次找 ，这样可以获取元素的下个元素
            SkipNode<T> one = search;
            SkipNode<T> two = one.getIndexes().get(curHeight);
            while (one != null) {
                if (data.compareTo(one.getVal()) > 0 && data.compareTo(two.getVal()) < 0) {
                    search(data, one, --curHeight);
                }
                one = two;
                two = one.getIndexes().get(curHeight);
            }
        }
        return success;
    }

    public static class SkipNode<T extends Comparable<T>> {
        /**
         * 链表的值
         */
        private T val;

        private Map<Integer, SkipNode<T>> indexes = new HashMap<>();

        /**
         * 链表前面的真实数据
         */
        private SkipNode prefix;

        /**
         * 链表后面真实的数据
         */
        private SkipNode next;

        public SkipNode() {
            this(null, null, null);
        }

        public SkipNode(T val, SkipNode prefix, SkipNode next) {
            this.val = val;
            this.prefix = prefix;
            this.next = next;
        }

        public Map<Integer, SkipNode<T>> getIndexes() {
            return indexes;
        }

        public void setIndexes(Map<Integer, SkipNode<T>> indexes) {
            this.indexes = indexes;
        }

        public SkipNode getPrefix() {
            return prefix;
        }

        public void setPrefix(SkipNode prefix) {
            this.prefix = prefix;
        }

        public SkipNode<T> getNext() {
            return next;
        }

        public void setNext(SkipNode<T> next) {
            this.next = next;
        }

        public T getVal() {
            return val;
        }

        public void setVal(T val) {
            this.val = val;
        }


    }


    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }
}
